package oj;

import java.util.HashMap;
import java.util.Map;

public class LC149 {
    //哈希表优化
    public int maxPoints(int[][] points) {
        int n=points.length;
        int ans=1;

        for(int i=0;i<n;i++){
            Map<String,Integer> map=new HashMap<>();
            int max=0;
            for(int j=i+1;j<n;j++){
                int x1=points[i][0], x2=points[i][1],y1=points[j][0],y2=points[j][1];
                int a=x1-y1,b=x2-y2;
                int k=gcd(a,b);
                String key=(a/k)+"_"+(b/k);
                map.put(key,map.getOrDefault(key,0)+1);
                max=Math.max(max,map.get(key));
            }
            ans=Math.max(ans,max+1);
        }
        return ans;
    }
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }


    //朴素解法
//    public int maxPoints(int[][] points) {
//        int n=points.length;
//        int ans=1;
//        for(int i=0;i<n;i++){
//            int[] x=points[i];
//            for(int j=i+1;j<n;j++){
//                int[] y=points[j];
//                int cnt=2;
//                for(int k=j+1;k<n;k++){
//                    int[] p=points[k];
//                    int s1=(y[1]-x[1])*(p[0]-y[0]);
//                    int s2=(p[1]-y[1])*(y[0]-x[0]);
//                    if(s1==s2) cnt++;
//
//                }
//                ans=Math.max(ans,cnt);
//            }
//        }
//        return ans;
//    }
}
